Odwiedziny

Limit pamięci: 128 MB

Bajtazar to wyjątkowy człowiek - przez ostatnie 21 lat był listonoszem, bankierem, łyżwiarzem, a nawet królem! Nic dziwnego, że ma mnóstwo znajomych. Niestety, ciągłe zmiany miejsc pracy sprawiły, że z wieloma z nich zaczął tracić kontakt... Czas to zmienić! Bajtazar wykona wielkie tournee po Bajtocji, aby odnowić stare znajomości.

W Bajtocji znajduje się miast, połączonych siecią dwukierunkowych dróg. Nasz bohater chce odwiedzić każde z miast kraju i ustalił już konkretną kolejność wizyt. Trasę między każdymi dwoma kolejnymi miastami pokona, korzystając z samochodu wypożyczonego w BMW (Bajtockiej Motoryzacji Wycieczkowej). Wypożyczenie każdego samochodu nie kosztuje nic, ale auta trzeba tankować - samochód o pojemności baku trzeba zatankować w mieście początkowym trasy i każdorazowo po przejechaniu dokładnie dróg. BMW, znając plan tournee Bajtazara oraz wiedząc, że każdą trasę będzie on chciał pokonać jak najszybciej, tak dobrało pojemność baków wypożyczanych samochodów, aby musiał on każdy z nich zatankować również w mieście docelowym.

Znając kolejność, w jakiej Bajtazar odwiedzi miasta, ceny tankowania w każdym z nich oraz pojemności baków wypożyczanych samochodów, wyznacz, ile będzie go kosztowało przejechanie każdej trasy.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę miast w Bajtocji. Miasta są numerowane od do . W kolejnym wierszu znajduje się ciąg liczb całkowitych () pooddzielanych pojedynczymi odstępami, oznaczających ceny paliwa w miastach Bajtocji: liczba oznacza koszt napełnienia baku dowolnego samochodu w mieście o numerze .

Dalej następuje wierszy zawierających opisy dróg w Bajtocji. W każdym z nich podane są dwie liczby całkowite , () oddzielone pojedynczym odstępem, oznaczające, że w Bajtocji istnieje dwukierunkowa droga łącząca miasta o numerach i .

W następnym wierszu znajduje się ciąg liczb całkowitych pooddzielanych pojedynczymi odstępami, opisujący kolejność, w jakiej Bajtazar ma zamiar odwiedzić miasta (każda z liczb od do pojawi się w tym ciągu dokładnie raz). Ostatni wiersz wejścia zawiera ciąg liczb całkowitych pooddzielanych pojedynczymi odstępami, opisujący pojemności baków wypożyczanych samochodów: liczba oznacza, że podczas przejazdu z miasta o numerze do miasta o numerze , Bajtazar będzie musiał tankować samochód co dróg. Możesz założyć, że zawsze dzieli odległość między tymi miastami.

W testach wartych punktów zachodzi dodatkowy warunek , a w testach wartych punktów zachodzi dodatkowy warunek .

Wyjście

Na standardowe wyjście Twój program powinien wypisać wierszy, w każdym po jednej liczbie całkowitej. Liczba w -tym wierszu ma oznaczać łączny koszt tankowania podczas trasy z miasta o numerze do miasta o numerze .

Przykład

Dla danych wejściowych:

5
1 2 3 4 5
1 2
2 3
3 4
3 5
4 1 5 2 3
1 3 1 1

poprawną odpowiedzią jest:

10
6
10
5

Autor zadania: Wojciech Nadara.